package com.vincent.exam.linkedList;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 利用双向链表，并且通过辅助链表头和尾实现了LRUcache
 * 核心思想是将最近使用（添加或者查询）的节点移动到头部
 * 超过容量限制capacity需要删除最后一个
 * 这里的map缓存所有节点，方便快速查找
 */
public class LRUCache {
    /**
     * 缓存所有节点，方便使用k获取到node
     */
    public Map<Integer, DoubleLinkedNode> map;
    /**
     * 辅助头节点，双链的头
     */
    public DoubleLinkedNode head;
    /**
     * 辅助尾节点，双链的尾
     */
    public DoubleLinkedNode tail;
    public int capacity;
    public int size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new DoubleLinkedNode(-1, -1);
        tail = new DoubleLinkedNode(-1, -1);
        head.next = tail;
        tail.pre = head;
        size = 0;
    }

    /**
     * 删除节点
     *
     * @param node
     */
    public void removeNode(DoubleLinkedNode node) {
        node.next.pre = node.pre;
        node.pre.next = node.next;
    }

    /**
     * 添加到最前面
     *
     * @param node
     */
    public void addToHead(DoubleLinkedNode node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    /**
     * 移动节点到最前面
     *
     * @param node
     */
    public void moveToHead(DoubleLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    /**
     * 移除最后一个节点
     *
     * @return
     */
    public DoubleLinkedNode removeLast() {
        DoubleLinkedNode last = tail.pre;
        removeNode(last);
        return last;
    }

    /**
     * 获取node，找得到返回值，找不到返回-1
     * @param key
     * @return
     */
    public int get(int key) {
        DoubleLinkedNode node = map.get(key);
        if (node == null) {
            return -1;
        }
        // 节点存在，查询后移动到头部，最近使用
        moveToHead(node);
        return node.v;
    }

    /**
     * 新增KV
     * @param key
     * @param val
     */
    public void put(int key, int val) {
        // 从缓存中获取
        DoubleLinkedNode node = map.get(key);
        if (node == null) {
            // 节点不存在，创建节点并添加到头部
            node = new DoubleLinkedNode(key, val);
            addToHead(node);
            map.put(key, node);
            size++;
            // 当长度大于容量，移除最后一个节点
            if (size > capacity) {
                DoubleLinkedNode last = removeLast();
                // 缓存中也需要删除
                map.remove(last.k);
                size--;
            }
        } else {
            // 节点存在直接更新值，并移动到头部
            node.v = val;
            moveToHead(node);
        }
    }

    public int[] showLRU(int[][] operators, int capacity){
        List<Integer> list = new ArrayList<>();
        LRUCache lruCache = new LRUCache(capacity);
        for (int[] operator : operators) {
            if (operator[0] == 1) {
                // 添加
                lruCache.put(operator[1],operator[2]);
            } else {
                // 查询
                list.add(lruCache.get(operator[1]));
            }
        }
        int[] log = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            log[i] = list.get(i);
        }
        return log;
    }
}
